#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    struct DataStruct
    {
    public:
        DataStruct(int K, vector<int> &nums) : size(K), balance(0)
        {
            for (int i = 0; i < K; ++i)
                small.push(nums[i]);
            for (int i = 0; i < K / 2; ++i)
                big.push(small.top()), small.pop();
        };
        void adjust(int left, vector<int> &nums)
        {
            //删除left元素
            //1.删除的元素位于中位数的左半边
            if (nums[left] <= small.top())
                mp[nums[left]]++, balance--;
            //2.删除的元素位于中位数的右半边
            else
                mp[nums[left]]++, balance++;
            //增加right元素
            int right = left + size;
            //1.增加的元素位于中位数的左半边
            if (nums[right] <= small.top())
                balance++, small.push(nums[right]);
            //2.增加的元素位于中位数的右半边
            else
                balance--, big.push(nums[right]);
            //两个堆元素平衡
            if (balance == 0)
                return;
            //small堆的元素比big堆多
            else if (balance == 2)
                big.push(small.top()), small.pop();
            //big堆的元素多于small堆
            else if (balance == -2)
                small.push(big.top()), big.pop();
            balance = 0;
        }
        double median()
        {
            while (small.empty() == false && mp[small.top()] > 0)
                mp[small.top()]--, small.pop();
            while (big.empty() == false && mp[big.top()] > 0)
                mp[big.top()]--, big.pop();
            if (size % 2 == 0)
                return ((double)small.top() + (double)big.top()) * 0.5;
            else
                return small.top();
        }

    private:
        priority_queue<int> small;
        priority_queue<int, vector<int>, greater<int>> big;
        unordered_map<int, int> mp;
        int size, balance;
    };

    vector<double> medianSlidingWindow(vector<int> &nums, int k)
    {
        DataStruct ds(k, nums);
        vector<double> ans;
        for (int i = 0; i + k < nums.size(); ++i)
        {
            ans.push_back(ds.median());
            ds.adjust(i, nums);
        }
        ans.push_back(ds.median());
        return ans;
    }
};